Exercici 7 (Tasca 5).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages),
coRE,
symmetric difference)
\mathbf{R}, \mathbf{RE}, \mathbf{coRE} i la diferència simètrica
Donats dos conjunts A i B, recordeu que la diferència simètrica de A i B és A\Delta B=(A\cup B)\setminus (A\cap B). Suposeu que A\Delta B\in \mathbf{R}.
- Si A\in \mathbf{R}, es compleix que B\in \mathbf{R}?
- Si A\in \mathbf{RE}, es compleix que B\in \mathbf{RE}?
- Si A\in \mathbf{coRE}, es compleix que B\in \mathbf{coRE}?